package com.Questions.DP;

import java.util.*;
/**
 * 分割回文串
 */
public class leetcode131 {
    boolean[][] f;// 动态规划数组
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans=new ArrayList<String>();
    int n; // 字符串的长度
    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n];
        for(int i = 0; i < n; ++i) {
            Arrays.fill(f[i],true);
        }

        for(int i = n - 1; i >= 0; --i) {
            for(int j = i + 1; j < n; ++j){// 这种写法很简介 且正确 避免了多次if else
                f[i][j] = (s.charAt(i) == s.charAt(j) && f[i+1][j-1] );
            }
        }// 动态规划 初始化 回文串 二维数组

        dfs(s,0);
        return ret;
    }

    private void dfs(String s, int i) {
        if (i == n) {// 答案字符串的长度 已经和 原字符串 长度相等 说明已经达到 答案的结果
            ret.add(new ArrayList<String>(ans));
            return;
        }

        for(int j = i; j < n; ++j){
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }

    // 给你一个字符串s 请你将s分割成一些子串 使每一个子串都是回文串
    // 返回s 所有可能的分割方案 （不能改变顺序 并且 这些字符在原字符串中必须是连续的）

    // 1 使用动态规划 预处理给定字符串 得到i到j是否是回文串
    // 2 在1 的基础上使用回溯 假设当前搜索到i s[0 i-1]位置的 所有字符已经被分割成若干个回文串
    // 并且已经将分割的结果放入了答案数组中 那么需要枚举下一个回文串的右边界j
    // 使得s[i j]是一个回文串

    // 因此我们可以从i开始 从小到大 依次枚举j 对于当前枚举值j 判断s[i][j]是否是回文串
}
